package com.michael.leetcode;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

/**
 * 155. 最小栈
 * 设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
    实现 MinStack 类:
    MinStack() 初始化堆栈对象。
    void push(int val) 将元素val推入堆栈。
    void pop() 删除堆栈顶部的元素。
    int top() 获取堆栈顶部的元素。
    int getMin() 获取堆栈中的最小元素。

    示例 1:
    输入：
    ["MinStack","push","push","push","getMin","pop","top","getMin"]
    [[],[-2],[0],[-3],[],[],[],[]]
    输出：
    [null,null,null,null,-3,null,0,-2]

    解释：
    MinStack minStack = new MinStack();
    minStack.push(-2);
    minStack.push(0);
    minStack.push(-3);
    minStack.getMin();   --> 返回 -3.
    minStack.pop();
    minStack.top();      --> 返回 0.
    minStack.getMin();   --> 返回 -2.

    提示：
    -231 <= val <= 231 - 1
    pop、top 和 getMin 操作总是在 非空栈 上调用
    push, pop, top, and getMin最多被调用 3 * 104 次
 */

public class MinStack_155 {

    private Deque<Integer> levelList;
    private Integer min;

    public MinStack_155() {
       levelList = new LinkedList<Integer>();
        min = null;
    }

    public void push(int val) {
        if (this.min == null){
            this.min = val;
        }else {
            this.min = Math.min(val, this.min);
        }

        levelList.offerLast(val);
    }

    public void pop() {
        levelList.removeLast();
        this.min = levelList.peekLast();
        // 更新最小值
        int size = levelList.size();
        for (int i = 0; i < size; i++) {
            Integer yy = levelList.pollLast();
            this.min = Math.min(yy, this.min);
            levelList.addFirst(yy);
        }
    }

    public int top() {
        return levelList.peekLast();
    }

    public int getMin() {
        return this.min;
    }

    public static void main(String[] args){
        MinStack_155 minStack = new MinStack_155();
        minStack.push(-2);
        minStack.push(0);
        minStack.push(-3);
        minStack.getMin();
        minStack.pop();
        minStack.top();
        minStack.getMin();
    }


    //使用两个Stack 操作
    class MinStack {
        private Stack<Integer> stack;
        private Stack<Integer> min_stack;
        public MinStack() {
            stack = new Stack<>();
            min_stack = new Stack<>();
        }
        public void push(int x) {
            stack.push(x);
            if(min_stack.isEmpty() || x <= min_stack.peek())
                min_stack.push(x);
        }
        public void pop() {
            if(stack.pop().equals(min_stack.peek()))
                min_stack.pop();
        }
        public int top() {
            return stack.peek();
        }
        public int getMin() {
            return min_stack.peek();
        }
    }
}